package leetcode

type ListNode struct {
	Val  int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	fastPtr, slowPtr := head, head
	for fastPtr.Next != nil && fastPtr.Next.Next != nil {
		fastPtr = fastPtr.Next.Next
		slowPtr = slowPtr.Next
		if fastPtr == slowPtr {
			fastPtr = head
			for fastPtr != slowPtr {
				fastPtr, slowPtr = fastPtr.Next, slowPtr.Next
			}
			return fastPtr
		}
	}
	return nil
}
